1. Field of the Invention
The invention relates to data sorting in computers and, more particularly, to a method and apparatus for data sorting in multiprocessors using sorting by intervals.
2. Background Description
The sorting of data is a very important and often used function in data processing systems. In such systems data is generally stored in files composed of records and the sorting process is governed by the value of one of the fields of the records, called the key. It is estimated that of the order of 20% of all computer running time is spent sorting. Improvement of the efficiency and speed of sorting methods in computers is therefore of substantial technical importance.
There are a large number of known sorting procedures. A general review of many of the known methods can be found in Knuth `The Art of Computer Programming--Sorting and Searching`, vol 3, (1973).
European patent application number EP 0 699 994 describes a recently developed sorting method which uses a statistical sampling approach to estimate the minimal range which contains all or almost all of the data. Using this technique which will be referred to in the following as `sorting by intervals`, sorting proceeds by dividing the overall range into many small sub-intervals and computing for each data item, using a fast operation, its subinterval. This technique has been theoretically shown to be linear in the number of elements to be sorted with a small coefficient. The development of this technique provided a significant improvement over previously existing sorting methods which required an expected sorting time of the order of Nlog.sub.2 N.